public class No047 {
    /**
     * 题目:在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0)。
     * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。
     * 给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
     */

    public int GetMaxValue(int[][] value) {
        int rows = value.length;
        if (rows == 0) return 0;
        int cols = value[0].length;
        // 记录从左上角到当前格子的最多价值
        // maxValue可以为一维数组 new int[cols]
        int[][] maxValue = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int left = 0;
                int up = 0;
                if (i > 0) up = maxValue[i - 1][j];
                if (j > 0) left = maxValue[i][j - 1];
                maxValue[i][j] = Math.max(left, up) + value[i][j];
            }
        }
        return maxValue[rows - 1][cols - 1];
    }
}
